/**
 *  @file IsSymmetric.c
 *  @brief 判断双向循环链表是否对称（回文）
 *  @details
 *      本程序定义了一个双向循环链表，并实现了插入、打印和判断链表是否对称的功能。
 *      判断方法为双指针法，从两端向中间遍历对比元素是否一致。
 *
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-07-23 15:31
 *  @version 1.0
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向循环链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个结点
    struct node *pre;       ///< 指向上一个结点
} node, *link;

// ------------------------- 基础操作函数 -------------------------

/**
 * @brief 创建一个新结点
 * @param value 要存储的值
 * @return 返回新建结点的指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->data = value;
    newNode->next = NULL;
    newNode->pre  = NULL;
    return newNode;
}

/**
 * @brief 初始化一个带头结点的双向循环链表
 * @param head 链表头指针的地址
 */
void initNode(link *head) {
    link newNode = createNode(0); // 头结点不存储有效数据
    if (newNode == NULL) return;

    *head = newNode;
    newNode->next = *head;  // 初始化成循环结构
    newNode->pre  = *head;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法，将新节点插入到头结点之后
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre  = head;

    head->next->pre = newNode;
    head->next = newNode;
}

/**
 * @brief 尾插法，将新节点插入到链表尾部
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link lastNode = head->pre;

    lastNode->next = newNode;
    newNode->pre = lastNode;
    newNode->next = head;
    head->pre = newNode;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 从头到尾打印链表（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == head) return;

    link cur = head->next;
    while (cur != head) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 判断对称性 -------------------------

/**
 * @brief 判断链表是否对称（回文）
 * @param head 链表头指针
 * @return 若链表是对称的则返回 true，否则返回 false
 */
bool isSymmetric(link head) {
    link right = head->next;   // 从左往右
    link left = head->pre;     // 从右往左

    // 当两个指针没有相遇（注意奇偶长度）
    // right != left 是奇数的时候， right->pre != left 是偶数的时候
    while (right != left && right->pre != left) {
        if (right->data != left->data) {
            return false;
        }
        right = right->next;
        left = left->pre;
    }
    return true;
}

// ------------------------- 测试主函数 -------------------------

int main() {
    link head = NULL;
    initNode(&head);

    // 示例链表：2 -> 3 -> 3 -> 2
    istTail(head, 2);
    istTail(head, 3);
    istTail(head, 3);
    istTail(head, 2);

    // 如需测试非对称情况，可取消注释：
    // istTail(head, 0);

    printList(head);

    bool flag = isSymmetric(head);
    if (flag) {
        printf("this link is symmetric\n");
    } else {
        printf("this link is not symmetric\n");
    }

    return 0;
}
